package com.practice.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import com.practice.util.BinaryTree;
import com.practice.util.BinaryTreeNode;

/**
 * Print out a binary tree in zigzag order, or leveled order, line by line.
 * (A)
 */
public class TreePrint {
	public static void main(String[] args) {
		int[] nodes = new int[]{1, 2, 4, 8, -1, -1, 9, -1, -1, 5, -1, 10, -1, -1,
				3, 6, -1, 11, -1, -1, 7, 12, -1, -1, 13, -1, -1};
		BinaryTree tree = BinaryTree.createTree(nodes);
		
		TreePrint tp = new TreePrint();
		tp.zigzag(tree);
		tp.level(tree);
		tp.preOrder(tree);
		tp.inOrder(tree);
		tp.postOrder(tree);
	}
	
	public void zigzag(BinaryTree tree) {
		Stack<BinaryTreeNode> left = new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> right = new Stack<BinaryTreeNode>();
		left.add(tree.getRoot());

		while (!left.isEmpty() || !right.isEmpty()) {
			while (!left.isEmpty()) {
				BinaryTreeNode node = left.pop();
				System.out.print(node.value() + "   ");
				
				if (node.left()!=null) right.push(node.left());
				if (node.right()!=null) right.push(node.right());
			}
			System.out.println();
			
			while (!right.isEmpty()) {
				BinaryTreeNode node = right.pop();
				System.out.print(node.value() + "   ");
				
				if (node.right()!=null) left.push(node.right());
				if (node.left()!=null) left.push(node.left());
			}
			System.out.println();
		}
	}
	
	public void level(BinaryTree tree) {
		Queue<BinaryTreeNode> current = new LinkedList<BinaryTreeNode>();
		Queue<BinaryTreeNode> next = new LinkedList<BinaryTreeNode>();
		current.add(tree.getRoot());
		
		while (!current.isEmpty()) {
			while (!current.isEmpty()) {
				BinaryTreeNode node = current.remove();
				System.out.print(node.value() + "   ");
				
				if (node.left() != null) next.add(node.left());
				if (node.right() != null) next.add(node.right());
			}
			System.out.println();
			
			Queue<BinaryTreeNode> temp = current;
			current = next;
			next = temp;
		}
	}
	
	public void preOrder(BinaryTree tree) {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		BinaryTreeNode root = tree.getRoot();
		stack.push(root);
		
		while (!stack.isEmpty()) {
			BinaryTreeNode node = stack.pop();
			System.out.print(node.value() + " ");
			if (node.right() != null) stack.push(node.right());
			if (node.left() != null) stack.push(node.left());
		}
		
		System.out.println();
	}
	
	public void inOrder(BinaryTree tree) {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		BinaryTreeNode current = tree.getRoot();
		
		while (current!=null || !stack.isEmpty()) {
			if (current != null) {
				stack.push(current);
				current = current.left();
			}
			else {
				current = stack.pop();
				System.out.print(current.value() + " ");
				current = current.right();
			}
		}
	}
	
	public void postOrder(BinaryTree tree) {
		Stack<BinaryTreeNode> first = new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> second = new Stack<BinaryTreeNode>();
		first.push(tree.getRoot());
		
		while (!first.isEmpty()) {
			BinaryTreeNode node = first.pop();
			second.push(node);
			
			if (node.left() != null) first.push(node.left());
			if (node.right() != null) first.push(node.right());
		}
		
		while (!second.isEmpty()) {
			System.out.print(second.pop().value() + " ");
		}
		System.out.println();
	}
}
